//
// Created by lm379 on 25-3-20.
//
#include<iostream>
using namespace std;

typedef struct {
    char *ch;
    int length;
}Str;

void getnext(Str subs, int next[]) {
    int t = 0, j = 1;
    next[1] = 0;
    while(j<subs.length) {
        if (t == 0 || subs.ch[t] == subs.ch[j]){
            next[++j] = ++t;
        } else {
            t = next[t];
        }
    }
}

int kmp(Str s, Str subs,int next[]) {
    int j = 1;
    int i = 1;
    while (i<=s.length&&j<=subs.length) {
        if (j == 0 || s.ch[i] == subs.ch[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j > subs.length)
        return i-subs.length;
    return 0;
}

bool initStr(Str &s, char *ch) {
    if (s.ch)
        free(s.ch);
    int length = 0;
    char *c = ch;
    while (*c) {
        length++;
        c++;
    }
    if (length == 0) {
        s.ch = NULL;
        s.length = 0;
        return false;
    }
    s.ch = (char*)malloc((length+2)*sizeof(char));
    if (s.ch == NULL)
        return false;
    c = ch;
    s.ch[0] = ' ';
    for (int i = 1;i<=length+1;i++,c++) {
        s.ch[i] = *c;
    }
    s.length = length;
    return true;
}

int main() {
    Str s,subs;
    char s1[] = "ABABABAABABAAABABAA";
    char s2[] = "ABABAAABABAA";
    if (!initStr(s,s1)) {
        cout<<"init s false";
    }
    if (!initStr(subs,s2)) {
        cout<<"init subs false";
    }
    int next[subs.length+1];
    getnext(subs,next);
    int loc = kmp(s,subs,next);
    cout << loc << endl;
    return 0;
}